\chapter{Introduction}
We are living in a time where electronic systems are pervasive in every aspect of our life, e.g., industrial automation, automobiles, telecommunication
systems, consumer electronics, military, agriculture, to name a few. New computing architectures are coming into the market every day to meet this huge
demand for programmable automated devices. Writing applications for these architectures, requires that the designer of such architectures, makes
 available a reliable compiler to begin with. The ever expanding market, places a huge demand for such devices and the need to beat competition, 
results in a very less turn-around time available for this task. So
manufacturers usually go for a retargetable compiler. A retargetable compiler is one, which can be configured to produce code for a new
architecture. GCC is one of the most popular retargetable compilers.


GCC stands for GNU Compiler Collection. GCC is an integrated distribution of compilers for several programming languages\cite{usinggcc}. 
GCC is one of the most widely used compilers for developing applications that run across several different architectures and 
operating systems. One of the strengths of GCC is, it is highly portable. This is because GCC was built so that it can be easily
ported to any machine where \emph{int} is at least a 32-bit type\cite{gccint}. GCC gets most of its information about the target 
machine from the Machine Description(MD) files written for that machine\cite{gccint}. GCC does not have any machine specific code, 
but has parameters which depend on the target machine's features\cite{gccint}. This is considered as an elegant way of 
alienating the machine specific details from the compiler design. 

\section{Motivation}
GCC parses the source language, converts it to an intermediate representation GIMPLE. After a few 
internal transformations, GCC converts the GIMPLE representation to another intermediate representation, RTL(Register Transfer Language). Finally, 
the RTL representation is converted to the target assembly code after performing a few transformations. MD files have the mapping from GIMPLE 
representation to RTL notation and from RTL notation to the machine's assembly code. So constructing the MD file for the target architecture forms the most important step
 in porting GCC. The MD file represents the machine instructions in an algebraic formula notation. Writing 
a MD file for a new architecture needs a good understanding of the RTL notation, and the instruction set of the target architecture, which 
is very difficult. So, in general an MD file for a new architecture is constructed from an MD file of a similar architecture by 
making modifications to suit the needs. Describing instructions in this method is  observed to be quite complex, verbose, 
repetitive and assumed to be more of a trial-and-error method.\cite{Khedker, kai-wei, Sameera}.

The MD files for popular architectures are typically huge(running into tens of thousands of lines).
 So, while writing MD files from scratch for a new
architecture, a single mistake will result in the compiler producing wrong or worse, inefficient code, without the user realizing it quickly. The problem 
could be fixed if the process of writing MD files is fully automated. But given the complexity of the architectures and the variety of architectures
available it is virtually impossible to fully automate this process. 

The MD files are huge because, they not only tell about the target machine, they also contain details for 
generating the expander (GIMPLE to RTL converter, explained later in Chapter 2) and recognizer(RTL to target instruction generator). Apart from this, they
have instructions that help in instruction scheduling, peephole optimizations, register allocation, etc.,\cite{gccworkshop}. RTL notation is used in achieving the above mentioned tasks. 
Hence, finding RTL expressions that are common across machines which can be reused in writing new machine descriptions will be of immense help.

\section{Contribution of This Thesis}

Typically, the intermediate languages used by compilers are assumed to be the language for an abstract machine. For a
class of architectures serving similar purposes, say typical general purpose processors, we expected the intermediate
language to show significant amount of similarities. So, if we can find out intermediate representations that are common 
across typical machines(minimal set), and group 
them logically, the process of retargeting can be made simpler and systematic. With the minimal set in hand, we 
believe parts of MD files for new
architectures can be generated automatically. Take for example, the scenario where we wanted to port GCC to a 
new general purpose processor. If we
 have this minimal set for the 
class of general purpose processors, we can start off by first writing MD instructions that map this minimal set to 
the target architecture. Once 
this is done, we can deal with those intermediate representations that are not part of the minimal set and is unique to 
this architecture and map 
them to the target architecture.



Davidson and Fraser\cite{Davidson} proposed a compiler architecture that was able to produce portable, optimizing compilers that can generate good code without the
need for a machine-dependent optimizer. Like many portable compiler models, even in Davidson Fraser model, 
the front end parses the source code and
produces an intermediate code. Machine-independent code optimizations are done on this
intermediate code(code for abstract machine). Retargeting involves, writing the mapping from abstract machine code to target machine code. 
They made
an interesting observation about the abstract machine. While deciding on this abstract machine, there are two choices. 
One is, letting the abstract
machine support a set of features which is almost equivalent to the union of sets of features supported by typical real world 
machines. Such abstract machines
are called \emph{union machines}. The second choice is, letting the abstract machine support a set of features which is roughly equivalent to the 
intersection of features offered by typical machines. Such a machine is called an \emph{intersection machine}. They argued that an intersection machine is
easier to implement and more stable than a union machine. We believe our hypothesis about a minimal set for a class of machines, is equivalent to Davidson and Fraser's 
idea for an intersection machine.

To verify our hypothesis we did the following,

\begin{enumerate}
 \item Read MD files for existing architectures from the back ends of GCC's source tree. We looked for patterns in them (RTL templates), which can be 
  identified as machine-independent. A MD file parser was written for this purpose.
 \item The collected patterns were classified logically, viz., arithmetic, logical, conditional branches, etc.
 \item We tested the possibility of instantiating these patterns with machine-specific values to get back the RTL templates back and succeeded.
 \item Rewrote MD files in terms of patterns and parameters, compiling them to get MD files with regular RTL templates from them.
\end{enumerate}

We tested the above approach on MD files from five architectures, ARM, i386, MIPS, SPARC and VAX and the results were promising.


\section{A Motivating Example}

Let us look at two define\_expand expressions, the first one is from MIPS and the next is from ARM. The examples given are modified for
ease of explanation and to avoid referring to complex concepts not yet introduced.

\begin{example}
\onehalfspacing
 \begin{verbatim}
 (define_expand "addsi3"
  [(set (match_operand:SI 0 "register_operand")
	(plus:GPR (match_operand:SI 1 "register_operand")
		  (match_operand:SI 2 "arith_operand")))]
  "")

(define_expand "addsi3"
  [(set (match_operand:SI 0 "s_register_operand" "")
	(plus:SI (match_operand:SI 1 "s_register_operand" "")
		 (match_operand:SI 2 "reg_or_int_operand" "")))]
  "TARGET_EITHER"
  "
  if (TARGET_32BIT && GET_CODE (operands[2]) == CONST_INT)
    {
      arm_split_constant (PLUS, SImode, NULL_RTX,
	                  INTVAL (operands[2]), operands[0], operands[1],
			  optimize && can_create_pseudo_p ());
      DONE;
    }
  "
)
\end{verbatim}
\end{example}

The RTL template of addsi3 expression from MIPS is depicted in figure \ref{fig:Figuremipsaddsi}. The table \ref{tab:mipsparam},
splits this RTL template into RTL pattern and parameters. 

 
\begin{figure}[htb!]
\centering%
\includegraphics[scale = 0.4]{Mips-addsi.pdf}
\caption{MIPS addsi3 Template}
\label{fig:Figuremipsaddsi}
\end{figure}

\begin{table}[htb!]
 \centering

\begin{tabular}{|l | l |}
\hline
addsi3-Pattern  & Parameter \\
\hline
\multirow{5}{*}{\includegraphics[scale = 0.4]{add-form.pdf}} & (match\_operand:SI 0 "register\_operand")\\
&\\
& SI \\
&\\
 & (match\_operand:SI 1 "register\_operand")\\
&\\
 & (match\_operand:SI 2 "arith\_operand")\\
\hline
\end{tabular}
\caption{MIPS Patterns and Parameters}
\label{tab:mipsparam}
\end{table}


Similarly, figure \ref{fig:Figurearmaddsi} depicts the RTL template of addsi3
expression from ARM, while table \ref{tab:armparam} shows the RTL pattern and parameters for the same. We can observe from the tables that
both these expressions, share the same pattern. They differ only in the parameters.

\begin{figure}[htb!]
\centering%
\includegraphics[scale = 0.4]{Arm-addsi.pdf}
\caption{ARM addsi3 Template}
\label{fig:Figurearmaddsi}
\end{figure}


\begin{table}[htb!]
 \centering

\begin{tabular}{|l | l |}
\hline
addsi3-Pattern  & Parameter \\
\hline
\multirow{5}{*}{\includegraphics[scale = 0.4]{add-form.pdf}} & (match\_operand:SI 0 "s\_register\_operand")\\
&\\
& SI \\
&\\
 & (match\_operand:SI 1 "s\_register\_operand" "")\\
&\\
 & (match\_operand:SI 2 "reg\_or\_int\_operand" "")\\
\hline
\end{tabular}
\caption{ARM Patterns and Parameters}
\label{tab:armparam}
\end{table}

We can see that, the pattern extracted in both the cases are the same.
The pattern,
extracted thus can go as part of the minimal set, more specifically to the list of arithmetic patterns. So while writing a new port, this is one of the
arithmetic patterns that needs to be filled with machine-specific values.



Another possibility arises from the above method of splitting the RTL templates into patterns and parameters. The MD file's RTL templates exhibit
significant amount of redundancies\cite{Khedker}. Patterns that repeats itself across several RTL templates can be declared once and 
used/instantiated with parameters every time it reoccurs. This can reduce the redundancies found in MD files. We'll look at this possibility in more detail in chapter 3.




\section{Organization of the Thesis}

The rest of this thesis is organized as follows. Chapter 2, reviews the compilation model of GCC and also the back-end organization of GCC.
Chapter 3, presents the methodology we have adopted. Chapter 4, presents the results and an analysis of the same. Chapter 5, gives a brief
description of the related work. The conclusion is provided in Chapter 6.



